package pers.qianyu.month_202012.date_20201217;

import java.util.*;

/**
 * 380. 常数时间插入、删除和获取随机元素
 * https://leetcode-cn.com/problems/insert-delete-getrandom-o1/
 *
 * @author mizzle rain
 * @date 2020年12月17日15:26:10
 */
public class RandomizedSet {
    private ArrayList<Integer> nums;
    private HashMap<Integer, Integer> map;
    private Random random;

    /**
     * Initialize your data structure here.
     */
    public RandomizedSet() {
        nums = new ArrayList<>();
        map = new HashMap<>();
        random = new Random();
    }

    /**
     * Inserts a value to the set. Returns true if the set did not already contain the specified element.
     */
    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        nums.add(val);
        map.put(val, nums.size() - 1);
        return true;
    }

    /**
     * Removes a value from the set. Returns true if the set contained the specified element.
     */
    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        int index = map.get(val);
        Integer tail = nums.get(nums.size() - 1);
        nums.add(index, tail);
        nums.remove(nums.size() - 1);
        map.put(tail, index);
        map.remove(val);
        return true;
    }

    /**
     * Get a random element from the set.
     */
    public int getRandom() {
        return nums.get(Math.abs(random.nextInt()) % nums.size());
    }
}